package com.whosly.demo.benchmark.sortalgorithms.shell;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 希尔排序（Shell Sort）
 *
 * @author fengyang
 * @date 2023/6/12 上午11:16
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class ShellSort
        implements ISortingAlgorithms
{

    /**
     * 希尔排序
     */
    public static final int M0 = 0;

    /**
     * 希尔排序
     */
    public static final int M1 = 1;

    /**
     * 实现方式
     */
    private int mode;

    public ShellSort()
    {
        this(M0);
    }

    public ShellSort(int mode)
    {
        this.mode = mode;
    }

    @Override
    public int[] sorting(int[] arr)
    {
        if (this.mode == M0) {
            return mode0(arr);
        }

        // default M1
        return mode1(arr);
    }

    /**
     * 希尔排序的其中一种实现， 循环方式略微差异。 性能更好。
     */
    private int[] mode0(int[] arr)
    {
        int len = arr.length, tmp, j;

        for (int gap = len / 2; gap >= 1; gap = gap / 2) { // gap 步长
            for (int i = gap; i < len; i++) { //组中的元素，从第二个数开始
                tmp = arr[i]; //将arr[i]赋给一个临时变量，然后和其同一组中并且在i前面的数字进行比较
                j = i - gap; //j为有序序列最后一位的位数
                while (j >= 0 && arr[j] > tmp) { //从后往前遍历。
                    //如果temp小于arr[j]的值，那么后移（注意这里不是arr[j + 1] = arr[j]了哈，因为要在每一组中进行直接插入排序）
                    arr[j + gap] = arr[j]; //向后移动 gap 位
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
        }

        return arr;
    }

    /**
     * 希尔排序的其中一种实现， 循环方式略微差异
     */
    private int[] mode1(int[] arr)
    {
        int gap= arr.length / 2;//步长
        int j, temp;
        while(gap != 0){//当gap等于0的时候，退出循环，数组实现有序
            for(int i = gap; i<arr.length; i++){
                temp = arr[i];//将arr[i]赋给一个临时变量，然后和其同一组中并且在i前面的数字进行比较
                for(j = i-gap; j>=0 ; j-=gap){//这一步近似于插入排序,将temp和i前面的而且是同一组的数字进行比较
                    if(arr[j] <= temp){//此处是升序排序
                        break;
                    }
                    arr[j+gap] = arr[j];//如果temp小于arr[j]的值，那么后移（注意这里不是arr[j + 1] = arr[j]了哈，因为要在每一组中进行直接插入排序）
                }
                arr[j+gap] = temp;
            }
            gap /= 2;
        }

        return arr;
    }
}
